GATE PYQ

GATE IT 2008

Q21.
Consider a computer with a 4-ways set-associative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8 KB. While accessing the memory location 0C795H by the CPU, the contents of the TAG field of the corresponding cache line is:

Q22.
If f(x) is defined as follows, what is the minimum value of f(x) for x \in (0, 2] ? f(x) = \begin{cases} \frac{25}{8x} \text{ when } x \leq \frac{3}{2} \\ x+ \frac{1}{x} \text { otherwise}\end{cases}

Q23.
In how many ways can b blue balls and r red balls be distributed in n distinct boxes?

Q24.
A binary tree with n>1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

Q25.
A binary tree with n>1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n_{3} can be expressed as

Q26.
The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which. I.MBCAFHPYK II.KAMCBYPFH III.MABCKYFPH Pick the true statement from the following.

Q27.
Consider the following languages. L_1 = \{a^i b^j c^k \mid i = j, k \geq 1\} L_2 = \{a^i b^j \mid j = 2i, i \geq 0\} Which of the following is true?

Q28.
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.\begin{array}{l} S \rightarrow a S \mid A \\ A \rightarrow a A b|b A a| \epsilon \end{array}For the string "aabbaab" how many steps are required to derive the string and how many parse trees are there?

Q29.
Consider a CFG with the following productions. S \to AA \mid B A \to 0A \mid A0 \mid 1 B \to 0B00 \mid 1 S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is:

Q30.
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.\begin{array}{l} S \rightarrow a S \mid A \\ A \rightarrow a A b|b A a| \epsilon \end{array}Which of the following strings is generated by the grammar above?